package offer;

public class _12_矩阵中的路径 {
    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'},
                          {'S', 'F', 'C', 'S'},
                          {'A', 'D', 'E', 'E'}};
        String word = "ABCCED";
        Solution solution = new _12_矩阵中的路径().new Solution();
        System.out.println(solution.exist(board, word));
    }

    class Solution {
        public boolean exist(char[][] board, String word) {
            boolean[][] visited = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if (dfs(board, word, 0, i, j, visited)) {
                        return true;
                    }
                }
            }
            return false;
        }
        private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) {
            if (board[i][j] != word.charAt(index)) {
                return false;
            } else if (index == word.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            boolean result = false;
            for (int[] direction : directions) {
                int newi = i + direction[0];
                int newj = j + direction[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                    if (!visited[newi][newj]) {
                        boolean flag = dfs(board, word, index + 1, newi, newj, visited);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }
    }
}
